\documentclass[12pt]{article}
\usepackage[spanish]{babel}
\usepackage{graphics}
\usepackage{float}
\usepackage{amssymb,amsmath}
\usepackage{graphicx}
 
\floatstyle{ruled}
\newfloat{program}{thp}{lop}
\floatname{program}{Programa}

\newtheorem{definicion}{Definici\'on}
\newtheorem{teorema}{Teorema}

\begin{document}

\title{Criptograf\'ia y Seguridad \\ Trabajo Pr\'actico Nro. 2}
\author{Gonzalo Bellver, Germ\'an Gross y Juan Mart\'in Pampliega}
\date{\today}
\maketitle

\begin{abstract}
En el siguiente trabajo se intenta comprender el mecanismo de autenticaci\'on por password seg\'un la metodolog\'ia usada en
sistemas tipo Linux. 
\end{abstract}


\section{Introducci\'on}
Para realizar el estudio deseado se tiene un archivo \texttt{ESPIA} cuya contrase\~na se tiene que averiguar.  El archivo ESPIA es un archivo de texto que ha sido encriptado utilizando AES-128-CBC. Hay un grupo de usuarios que tiene acceso al contenido del mismo. \\

Para ello, se dispone de un archivo similar al \texttt{/etc/shadow} de Linux. Este archivo, llamado \texttt{CLAVES}, contiene una linea de texto por cada usuario que puede acceder al archivo. La linea esta compuesta por el nombre de usuario, y un vuelco hexadecimal. \\

El vuelco hexadecimal esta construido de la siguiente forma: \\
\begin{enumerate}
	\item Calcular k = SHA1( nombre de usuario $||$ clave ) \\
	\item Descartar los \'ultimos 32 bits de k (qued\'andose con 128 bits) \\
	\item Aplicar un XOR bit a bit entre la clave del archivo \texttt{ESPIA} y los bits generados \\
	\item Convertir los 16 bytes resultantes a un string de 32 caracteres, expandiendo cada byte en dos caracteres que lo representen en hexadecimal \\
\end{enumerate}

Para acceder al archivo, el sistema toma la clave del usuario, le antepone el nombre de
usuario, calcula el hash, descarta los \'ultimos 32 bits, y aplica un XOR bit a bit con el vuelco que
se encuentra en el archivo.\\

Con la clave candidata obtenida desencripta el primer bloque del archivo \texttt{ESPIA}. Si todos
los bytes est\'an comprendidos en el espectro ASCII (32-127), se sigue desencintando el archivo.
Sino, se informa que la clave es incorrecta. \\

Se desea averiguar en primer lugar la contrase\~na del archivo esp\'ia. Luego se desencripta los contenidos del mismo y de esta forma se obtiene \emph{Lugar de Reuni\'on y (n, umbral, p)}. Se intercambian con otros dos grupos que tengan el mismo lugar de reuni\'on los pares \emph{(n, umbral)}. Finalmente se obtiene el secreto de Shamir. 

\section{Obtenci\'on de la clave del archivo esp\'ia}
Para esto se realiza un ataque diccionario sobre las contrase\~nas de los usuarios. Se  obtiene una posible contrase\~na del diccionario, se le concatena el nombre de usuario adelante. Luego se calcula el SHA1 del string obtenido y se descartan los \'ultimos 32 bytes. Finalmente se obtiene una posible clave esp\'ia realizando un XOR entre el nuevo hash generado y el vuelco obtenido del archivo de usuarios de cada usuario, se intena desencriptar el archivo y si se obtienen todos caracteres ASCII se muestra el resultado en pantalla y finaliza el programa. \\

El diccionario utilizado es un archivo que contiene inicialmente un listado de claves comunes y posteriormente un listado de un diccionario en castellano sin las palabras que tienen \~N. Para generar las posibles claves se itera por todo el archivo probando una palabra por vez, si la palabra no es la clave, se prueba con la misma agregandole los numeros del 1 al 10 primero adelante y luego atr\'as. Si ninguna de estas posibilidades es la clave correcta se contin\'ua con la siguiente palabra del diccionario. \\

El resultado al correr el programa fue:\\
\texttt{Cataratas del Iguazu Misiones,(3, 455, 1721)}\\
\texttt{Password found: 'qwerty1'}\\
\texttt{File cracked!}\\

\section{Obtenci\'on del secreto de Shamir}

Al comunicarse con otros grupos se obtuvieron los pares de los grupos 1, 2 y 4 (cuyo lugar de reuni\'on coincide con el nuestro) y se obtuvieron los pares:\\
\texttt{(1, 1534)}\\
\texttt{(2, 611)}\\
\texttt{(4, 1066)}\\

Para obtener el secreto de Shamir se eligieron los pares de los grupos 1 y 2 conjuntamente con el nuestro (grupo 3). Finalmente se utiliza el programa \texttt{shamir} al cual se le pasa interactivamente la cantidad de de puntos que se van a interpolar (3 en este caso), luego el primo \texttt{p} (1721 en este caso) y finalmente los pares de puntos. Con estos datos realiza el polinomio interpolador de Lagrange y evalu\'andolo en 0 se obtiene el secreto de Shamir luego de hacer m\'odulo \texttt{p} al resltado.\\
Finalmente el resultado obtenido fue: \\
\\
\texttt{The value of the Shamir secret is: 1503}\\
\texttt{==The date is March 15==}\\

\section{Resultados extra}
Utilizando el programa aplicado para obtener la clave del archivo esp\'ia se obtuvieron los resultados de los otros archivos encriptados para los otros grupos los cuales son los siguientes:\\

\texttt{
	Grupo 1:\\
	Cataratas del Iguazu Misiones,(1, 1534, 1721)\\
	Password found: 'qwerty1'\\
	\\
	Grupo 2:\\
	Cataratas del Iguazu Misiones,(2, 611, 1721)\\
	Password found: 'windows'\\
	\\
	Grupo 4:\\
	Cataratas del Iguazu Misiones,(4, 1066, 1721)\\
	Password found: 'qwerty1'\\
	\\
	Grupo 5:\\
	Glaciar Perito Moreno Santa Cruz,(1, 1390, 2621)\\
	Password found: 'qwerty1'\\
	\\
	Grupo 6:\\
	Glaciar Perito Moreno Santa Cruz,(2, 1648, 2621)\\
	Password found: '1mejor'\\
	\\
	Grupo 7:\\
	Glaciar Perito Moreno Santa Cruz,(3, 664, 2621)\\
	Password found: '1mejor'\\
	\\
	Grupo 8:\\
	Glaciar Perito Moreno Santa Cruz,(4, 1059, 2621)\\
	Password found: '1mejor'\\
	\\
	Grupo 9:\\
	Valle de la Luna San Juan,(1, 862, 2357)\\
	Password found: '1mejor'\\
	\\
	Grupo 10:\\
	Valle de la Luna San Juan,(2, 656, 2357)\\
	Password found: 'windows'\\
	\\
	Grupo 11:\\
	Valle de la Luna San Juan,(3, 1484, 2357)\\
	Password found: 'windows'\\
	\\
	Grupo 12:\\
	Valle de la Luna San Juan,(4, 989, 2357)\\
	Password found: 'qwerty1'\\
	\\
}

\section{Conclusi\'on}
 Se puede concluir que el m\'etodo de autenticaci\'on de passwords en Linux resulta tan robusto como las contrase\~nas elegidas cuando se tiene un atacante que puede realizar un ataque de diccionario sobre las posibles contrase\~nas. Es por esto que es muy importante tratar de elegir palabras que no se encuentren dentro de un diccionario o de un listado de claves comunes, o que sean peque\~nas variaciones de las mismas.\\
Por otro lado, se observ\'o que el secreto de Shamir resulta muy adecuado para compartir secretos para los cuales se necesitan claves de varias personas para conocer su contenido.\\
 
\end{document}
